package STO_14_1;

import java.util.Arrays;

public class Solution {
	public int cuttingRope(int n) {
		if (n <= 3) {
			return n - 1;
		}
		int a = n / 3, b = n % 3;
		if (b == 0) {
			return (int) Math.pow(3, a);
		}
		if (b == 1) {
			return (int) Math.pow(3, a - 1) * 4;
		}
		return (int) Math.pow(3, a) * 2;
	}

	public int cuttingRope_DP(int n) {
		int[] dp = new int[1000];
		Arrays.fill(dp, 0);
		dp[2] = 1;
		int res = -1;
		for (int i = 3; i < n + 1; i++) {
			for (int j = i - 1; j >= 0; j--) {
				dp[i] = Math.max(dp[i], Math.max((i - j) * j, j * dp[i - j]));
			}
		}

		return dp[n];
	}

}
